package com.leetcode.partition5;

import java.util.Arrays;

/**
 * @author `RKC`
 * @date 2021/10/14 9:15
 */
public class LC403青蛙过河 {

    public static boolean canCross(int[] stones) {
        return dynamicProgramming(stones);
//        return memoization(stones, 0, 0, new Boolean[stones.length][stones.length]);
    }

    public static void main(String[] args) {
        int[] stones = {0, 1, 3, 5, 6, 8, 12, 17};
//        int[] stones = {0, 2};
        System.out.println(canCross(stones));
    }

    private static boolean memoization(int[] stones, int curIndex, int prevStep, Boolean[][] memo) {
        if (curIndex == stones.length - 1) return true;
        //memo[i][j]：能够通过跳跃j步到当前i位置
        if (memo[curIndex][prevStep] != null) return memo[curIndex][prevStep];
        //当前能够跳跃的步数只能是prevStep-1、prevStep和prevStep+1
        for (int nextStep = prevStep - 1; nextStep <= prevStep + 1; nextStep++) {
            if (nextStep <= 0) continue;
            //查询能否根据当前选择的nextStep跳跃到下一步，如果能跳到下一步，返回下一步索引大于等于0
            int nextIndex = Arrays.binarySearch(stones, curIndex + 1, stones.length, nextStep + stones[curIndex]);
            if (nextIndex >= 0 && memoization(stones, nextIndex, nextStep, memo)) {
                memo[curIndex][prevStep] = true;
                return memo[curIndex][prevStep];
            }
        }
        return memo[curIndex][prevStep] = false;
    }

    private static boolean dynamicProgramming(int[] stones) {
        //dp[i][k]：能否通过上一次跳跃k步到达当前位置i
        boolean[][] dp = new boolean[stones.length][stones.length];
        dp[0][0] = true;
        //因为每次最多增长1步，因此在i石头上时，步数不可能超过i，进行预判断
        for (int i = 1; i < stones.length; i++) {
            if (stones[i] - stones[i - 1] > i) {
                return false;
            }
        }
        for (int i = 1; i < stones.length; i++) {
            for (int j = i - 1; j >= 0; j--) {
                int k = stones[i] - stones[j];
                //j个石头时，最多下一步可以跳跃到j+1步，如果i和j相隔的距离超过了最大能跳跃的步数，则为dp[i][k]=false
                if (k > j + 1) break;
                //当前位置可以由i-(k-1)、i-k、i-(k+1)跳过来，如果有任意位置可以到达则认为是true
                dp[i][k] = dp[j][k - 1] || dp[j][k] || dp[j][k + 1];
                //只要有任意一种策略跳跃到了最后一个位置，就认为是成功的
                if (dp[i][k] && i == stones.length - 1) {
                    return true;
                }
            }
        }
        return false;
    }
}
